package com.example.demo.剑指offer;

import java.util.Arrays;

/**
 * @author：zzc
 * @date: 2022/8/19
 */
public class 调整数组顺序使奇数位于偶数前面 {

    //输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
    //
    //
    //
    //示例：
    //
    //输入：nums = [1,2,3,4]
    //输出：[1,3,2,4]
    //注：[3,1,2,4] 也是正确的答案之一。

    //解法
    //双指针
    //
    //定义两个指针，分别指向数组左右边缘。
    //
    //查看左指针所指向的元素。
    //若为 奇数，则左指针往右移动。
    //若为 偶数，则与右指针交换元素，并将右指针往左移动。
    //重复该过程，直到左指针超过右指针。

    static class Solution {

        public static int[] exchange(int[] nums) {
            int p = 0, q = nums.length - 1;
            while (p < q) {
                if ((nums[p] & 1) == 1) {
                    ++p;
                    continue;
                }
                if ((nums[q] & 1) == 0) {
                    --q;
                    continue;
                }
                swap(nums, p, q);
            }
            return nums;
        }

        private static void swap(int[] nums, int p, int q) {
            int t = nums[p];
            nums[p] = nums[q];
            nums[q] = t;
        }

        public static void main(String[] args) {

            System.out.println(Arrays.toString(exchange(new int[]{1, 2, 4, 3, 21, 2, 4, 5, 2, 3, 1, 2})));
        }
    }

}
